/*
 * @lc app=leetcode.cn id=2039 lang=typescript
 *
 * [2039] 网络空闲的时刻
 */

// @lc code=start
interface Status {
  idx: number;
  dist: number;
}

function networkBecomesIdle(edges: number[][], patience: number[]): number {
  const n = patience.length;
  const adj = new Array(n).fill(0).map(() => []);
  const visited = new Array(n).fill(0);
  // 构建邻接矩阵
  for (const v of edges) {
    adj[v[0]].push(v[1]);
    adj[v[1]].push(v[0]);
  }

  // 广度优先搜索最短路径
  const queue: Status[] = [];
  let ans = 0;
  // 初始化
  queue.push({ idx: 0, dist: 0 });
  visited[0] = 1;
  while (queue.length) {
    const curr = queue.shift()!;
    for (const next of adj[curr.idx]) {
      if (visited[next]) continue;
      const dist = curr.dist + 1;
      queue.push({ idx: next, dist });
      visited[next] = 1;
      const time = patience[next] * (((2 * dist - 1) / patience[next]) >> 0) + (2 * dist + 1);
      ans = Math.max(ans, time);
    }
  }

  return ans;
}
// @lc code=end
